use crate::offer::Solution;

#[allow(unused)]
impl Solution {
    pub fn single_numbers(nums: Vec<i32>) -> Vec<i32> {
        // 方法1
        // 我们先思考一下如果只有一个不同的数，其他都为两个相同的
        // 那么就很简单的可以处理成为 a^a^b^b^c = c
        // 也就是说利用异或可以揪出那个不同的
        // 现在有两个不同的，那这里我们想要是把两个不同的分在不同的数组里面就好了，就可以用异或处理了
        // 所以，怎么分就成了关键，这里我们通过位来把数字分组
        // 我们先把所有的数字都异或可以得到两个不同的数字的异或结果是n = a ^ b
        // 那么我们如果找到n中从最右边的位开始第一个不为0的那个数字m就是分组的关键
        // 这样我们可以通过nums的每个数字x与这个m进行与操作，这样就有0和不为0两个组
        // 然后把两个组中的数字做异或就可以得到a和b了
        // 例如： 4，1，4，6
        // 4：0100
        // 1：0001
        // 4：0100
        // 6：0110
        // 全部异或得到n = 0111
        // 找到第一个不为0的数字m，就是0001
        // 现在开始分组：
        // 4： 0100  & 0001 = 0
        // 1： 0001  & 0001 = 1
        // 6： 0110  & 0001 = 0
        // 得到分组： 4，4，6 和 1
        // 然后我们分别异或，得到6和1，就是结果
        // 这里由于要求空间为1，所以我们分组的时候直接进行异或运算即可
        // AC 0ms 2mb
        let mut n = nums.iter().fold(0, |acc, x| acc ^ x);
        let mut m = 1;
        while m & n == 0 { m <<= 1; }
        let mut answer = vec![0, 0];
        for x in nums {
            if x & m == 0 { answer[0] ^= x; } else { answer[1] ^= x; }
        }
        answer
    }
}
